package pishen;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.apache.commons.collections15.Factory;

import edu.uci.ics.jung.graph.Graph;

public class GraphEvolver {
	private Graph<Node, Edge> graph;
	private int time, initialSize;
	private List<Node> targetList;
	private int[] lifeTime = new int[100];
	
	public GraphEvolver(Graph<Node, Edge> g){
		graph = g;
		targetList = new LinkedList<Node>();
	}
	
	public void initialize(int size){
		//create a clique
		initialSize = size;
		List<Node> nodeList = new ArrayList<Node>();
		for(int i = 0; i < initialSize; i++){
			Node newNode = new Node(); //the life of the node is decided when creating it
			while(newNode.getRemainLife() == 0){
				newNode = new Node();
			}
			graph.addVertex(newNode);
			nodeList.add(newNode);
			for(int j = 0; j < initialSize - 1; j++){
				targetList.add(newNode);
			}
		}
		for(Node sourceNode: graph.getVertices()){
			for(Node targetNode: graph.getVertices()){
				if(targetNode != sourceNode && graph.findEdge(sourceNode, targetNode) == null){
					graph.addEdge(new Edge(), sourceNode, targetNode);
				}
			}
		}
	}
	
	public void step(){
		time++;
		
		//remove nodes with remainLife = 0 and subtract other nodes' remainLife by 1
		int removedNodes = removeNodes();
		
		//add (1 + removedNodes * 3) new nodes in this time frame
		for(int i = 0; i < 1 + removedNodes * 3; i++){
			addByModifiedBA();
			//addBySimpleBA();
		}
		
		//gain assortativity
		gainAssortativity(removedNodes);
	}
	
	private int removeNodes(){
		List<Node> nodeToRemove = new ArrayList<Node>();
		for(Node node: graph.getVertices()){
			if(node.getRemainLife() == 0){
				nodeToRemove.add(node);
				ArrayList<Node> target = new ArrayList<Node>();
				target.add(node);
				targetList.removeAll(target);
				lifeTime[node.getGivenLife()]++;
			}else{
				node.setRemainLife(node.getRemainLife() - 1);
			}
		}
		for(Node node: nodeToRemove){
			graph.removeVertex(node);
		}
		
		return nodeToRemove.size();
	}
	
	private void addBySimpleBA(){
		Node newNode = new Node();
		int numOfEdgeToAdd = initialSize;
		graph.addVertex(newNode);
		Node[] nodeBuffer = new Node[numOfEdgeToAdd];
		
		for(int j = 0; j < numOfEdgeToAdd; j++){
			Node target = targetList.get((int)(targetList.size() * Math.random()));
			graph.addEdge(new Edge(), newNode, target);
			nodeBuffer[j] = target;
			ArrayList<Node> targetCollection = new ArrayList<Node>();
			targetCollection.add(target);
			targetList.removeAll(targetCollection);
		}
		//restore targetList
		for(int j = 0; j < numOfEdgeToAdd; j++){
			for(int k = 0; k < graph.degree(nodeBuffer[j]); k++){
				targetList.add(nodeBuffer[j]);
			}
		}
		for(int j = 0; j < numOfEdgeToAdd; j++){
			targetList.add(newNode);
		}
	}
	
	private void addByModifiedBA(){
		Node newNode = new Node();
		int numOfEdgeToAdd = initialSize;
		graph.addVertex(newNode);
		ArrayList<Node> connectedNodeList = new ArrayList<Node>();
		Node target = null;
		
		for(int i = 0; i < numOfEdgeToAdd; i++){
			if(i != 0){
				//find a node from the neighbors of previous connected node to connect
				ArrayList<Node> neighborTargetList = new ArrayList<Node>();
				for(Node node: graph.getNeighbors(target)){
					if(node != newNode && graph.findEdge(newNode, node) == null){
						for(int k = 0; k < graph.degree(node); k++){
							neighborTargetList.add(node);
						}
					}
				}
				
				if(neighborTargetList.size() > 0){
					target = neighborTargetList.get((int)(neighborTargetList.size() * Math.random()));
				}else{
					target = null;
				}
			}

			if(target == null){
				//find a node from targetList by BA
				target = targetList.get((int)(targetList.size() * Math.random()));
			}
			
			//connect the edge
			graph.addEdge(new Edge(), newNode, target);
			
			//remove this node from targetList
			ArrayList<Node> targetCollection = new ArrayList<Node>();
			targetCollection.add(target);
			targetList.removeAll(targetCollection);
			//backup
			connectedNodeList.add(target);
		}

		//restore the removed node in targetList from backup
		for(Node node: connectedNodeList){
			for(int i = 0; i < graph.degree(node); i++){
				targetList.add(node);
			}
		}
		//add newNode to targetList
		for(int j = 0; j < numOfEdgeToAdd; j++){
			targetList.add(newNode);
		}
	}
	
	private void gainAssortativity(int iteration){
		AssortativityGenerator<Node, Edge> assorGen = new AssortativityGenerator<Node, Edge>(graph, new Factory<Edge>(){
			public Edge create(){
				return new Edge();
			}
		}, iteration);
		assorGen.run();
	}
	
	public int getTime(){
		return time;
	}
	
	public int[] getLifeTime(){
		return lifeTime;
	}
}
